﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using Twodi.Aspect.Interfaces;
using Microsoft.Xna.Framework;

namespace Twodi.Structs
{
    /// <summary>
    /// Representação de uma QuadTree genérica.
    /// </summary>
    /// <typeparam name="T">Tipo dos objetos, aonde deve ter posição e tamanho.</typeparam>
    public class Quadtree<T> where T : IPositionAspect, ISizeAspect
    {
        /// <summary>
        /// Construtor do QuadTree.
        /// Será considerado o nivel atual zero (0), nivel máximo cinco (5), posição (0,0) e capacidade dez (10).
        /// </summary>
        /// <param name="size">Tamanho do QuadTree.</param>
        public Quadtree(Vector2 size)
            : this(10, Vector2.Zero, size)
        {

        }

        /// <summary>
        /// Construtor do QuadTree.
        /// Será considerado o nivel atual zero (0), nivel máximo cinco (5) e posição (0,0).
        /// </summary>
        /// <param name="capacity">Capacidade atual da QuadTree para gerar Split.</param>
        /// <param name="size">Tamanho do QuadTree.</param>
        public Quadtree(int capacity, Vector2 size)
            : this(capacity, Vector2.Zero, size)
        {

        }

        /// <summary>
        /// Construtor do QuadTree.
        /// Será considerado o nivel atual zero (0) e nivel máximo cinco (5).
        /// </summary>
        /// <param name="capacity">Capacidade atual da QuadTree para gerar Split.</param>
        /// <param name="position">Posição do QuadTree.</param>
        /// <param name="size">Tamanho do QuadTree.</param>
        public Quadtree(int capacity, Vector2 position, Vector2 size)
            : this(capacity, 5, position, size)
        {

        }

        /// <summary>
        /// Construtor do QuadTree.
        /// Será considerado o nivel atual zero (0).
        /// </summary>
        /// <param name="capacity">Capacidade atual da QuadTree para gerar Split.</param>
        /// <param name="maxLevel">Nivel máximo para geração de Split.</param>
        /// <param name="position">Posição do QuadTree.</param>
        /// <param name="size">Tamanho do QuadTree.</param>
        public Quadtree(int capacity, int maxLevel, Vector2 position, Vector2 size)
            : this(0, capacity, maxLevel, position, size)
        {

        }

        /// <summary>
        /// Construtor do QuadTree.
        /// Será considerado o nivel atual zero (0) e nivel maximo cinco (5).
        /// </summary>
        /// <param name="capacity">Capacidade atual da QuadTree para gerar Split.</param>
        /// <param name="bounds">Definição do QuadTree.</param>
        public Quadtree(int capacity, Microsoft.Xna.Framework.Rectangle bounds)
            : this(capacity, new Vector2(bounds.X, bounds.Y), new Vector2(bounds.Width, bounds.Height))
        {

        }

        /// <summary>
        /// Construtor do QuadTree.
        /// Será considerado o nivel atual zero (0).
        /// </summary>
        /// <param name="capacity">Capacidade atual da QuadTree para gerar Split.</param>
        /// <param name="maxLevel">Nivel máximo para geração de Split.</param>
        /// <param name="bounds">Definição do QuadTree.</param>
        public Quadtree(int capacity, int maxLevel, Microsoft.Xna.Framework.Rectangle bounds) :
            this(capacity, maxLevel, new Vector2(bounds.X, bounds.Y), new Vector2(bounds.Width, bounds.Height))
        {

        }

        /// <summary>
        /// Construtor padrão do QuadTree.
        /// </summary>
        /// <param name="level">Nivel da QuadTree.</param>
        /// <param name="capacity">Capacidade atual da QuadTree para gerar Split.</param>
        /// <param name="maxLevel">Nivel máximo para geração de Split.</param>
        /// <param name="position">Posição do QuadTree.</param>
        /// <param name="size">Tamanho do QuadTree.</param>
        public Quadtree(int level, int capacity, int maxLevel, Vector2 position, Vector2 size)
        {
            Level = level;
            Capacity = capacity;
            MaxLevel = maxLevel;
            Objects = new List<T>();
            Bounds = new RectangleF(position.X, position.Y, size.X, size.Y);
        }

        /// <summary>
        /// Limpar objetos na QuadTree.
        /// </summary>
        public void Clear()
        {
            Objects.Clear();
            if (TopLeft != null) TopLeft.Clear();
            if (TopRight != null) TopRight.Clear();
            if (BottomLeft != null) BottomLeft.Clear();
            if (BottomRight != null) BottomRight.Clear();
        }


        /// <summary>
        /// Criar 4 filhos (sub-QuadTree) com tamanho de 1/4 do pai.
        /// </summary>
        private void Split()
        {
            float subWidth = Bounds.Width / 2;
            float subHeight = Bounds.Height / 2;
            int subLevel = Level + 1;

            Vector2 position = new Vector2(Bounds.X, Bounds.Y);
            Vector2 size = new Vector2(subWidth, subHeight);

            TopLeft = new Quadtree<T>(subLevel, position, size);
            TopRight = new Quadtree<T>(subLevel, position + (size * Vector2.UnitX), size);
            BottomLeft = new Quadtree<T>(subLevel, position + (size * Vector2.UnitY), size);
            BottomRight = new Quadtree<T>(subLevel, position + size, size);
        }

        /// <summary>
        /// Localizar qual QuadTree filho o componente s eencontra.
        /// </summary>
        /// <param name="position">Posição do objeto.</param>
        /// <param name="size">Tamanho do objeto.</param>
        /// <param name="origin">Posição de Origem do objeto, se possuir.</param>
        /// <returns>Retorna qual Sub-QuadTree o objeto provavelmente se encontra.</returns>
        private Quadtree<T> Find(Vector2 position, Vector2 size, Vector2 origin = new Vector2())
        {
            RectangleF pRect = new RectangleF(position.X, position.Y, size.X, size.Y);

            pRect.X -= origin.X;
            pRect.Y -= origin.Y;

            double verticalMidpoint = Bounds.X + (Bounds.Width / 2);
            double horizontalMidpoint = Bounds.Y + (Bounds.Height / 2);

            // Object can completely fit within the top quadrants
            bool topQuadrant = (pRect.Y < horizontalMidpoint && pRect.Y + pRect.Height < horizontalMidpoint);

            // Object can completely fit within the bottom quadrants
            bool bottomQuadrant = (pRect.Y > horizontalMidpoint);

            // Object can completely fit within the left quadrants
            if (pRect.X < verticalMidpoint && pRect.X + pRect.Width < verticalMidpoint)
            {
                if (topQuadrant)
                {
                    return TopLeft;
                }
                else if (bottomQuadrant)
                {
                    return BottomLeft;
                }
            }

            // Object can completely fit within the right quadrants
            else if (pRect.X > verticalMidpoint)
            {
                if (topQuadrant)
                {
                    return TopRight;
                }
                else if (bottomQuadrant)
                {
                    return BottomRight;
                }
            }

            return null;
        }

        /// <summary>
        /// Adicionar objeto no QuadTree ou seus respectivos filhos.
        /// </summary>
        /// <param name="obj">Objeto a ser usado como referencia.</param>
        public void Add(T obj)
        {
            if (!IsLeaf)
            {
                var node = Find(obj.PositionProperties.Position, obj.SizeProperties.Size);
                if (node != null)
                {
                    node.Add(obj);
                    return;
                }
            }

            Objects.Add(obj);

            if (Objects.Count > Capacity && Level < MaxLevel)
            {
                if (IsLeaf)
                {
                    Split();
                }

                int i = 0;
                while (i < Objects.Count)
                {
                    var node = Find(Objects[i].PositionProperties.Position, Objects[i].SizeProperties.Size);
                    if (node != null)
                    {
                        T tempObj = Objects[i];
                        Objects.Remove(tempObj);
                        node.Add(tempObj);
                    }
                    else
                    {
                        i++;
                    }
                }
            }
        }

        /// <summary>
        /// Retornar lista de objetos que podem colidir com o componente, tirando ele proprio.
        /// </summary>
        /// <param name="obj">Objeto a ser usado como referencia.</param>
        /// <param name="origin">Posição de Origem do objeto, se possuir.</param>
        /// <returns>Lista de possiveis componentes que podem gerar colisão.</returns>
        public List<T> Retrieve(T obj, Vector2 origin = new Vector2())
        {
            List<T> returnObjects = new List<T>();

            Retrieve(returnObjects, obj.PositionProperties.Position, obj.SizeProperties.Size, origin);

            returnObjects.RemoveAll(retObj => retObj.Equals(obj));

            return returnObjects;
        }

        /// <summary>
        /// Retornar lista de objetos que podem colidir com algum componente na posição, com tamanho e origem especificos.
        /// </summary>
        /// <param name="position">Posição a ser levada em consideração.</param>
        /// <param name="size">Tamanho a ser levado em consideração.</param>
        /// <param name="origin">Posição de Origem do objeto, se possuir.</param>
        /// <returns>Lista de possiveis componentes que podem gerar colisão.</returns>
        public List<T> Retrieve(Vector2 position, Vector2 size, Vector2 origin = new Vector2())
        {
            List<T> returnObjects = new List<T>();

            Retrieve(returnObjects, position, size, origin);

            return returnObjects;
        }

        /// <summary>
        /// Retornar lista de objetos que podem colidir com algum componente na posição, com tamanho e origem especificos.
        /// </summary>
        /// <param name="returnObjects">Lista que será retornada populada.</param>
        /// <param name="position">Posição a ser levada em consideração.</param>
        /// <param name="size">Tamanho a ser levado em consideração.</param>
        /// <param name="origin">Posição de Origem do objeto, se possuir.</param>
        /// <returns>Lista de possiveis componentes que podem gerar colisão.</returns>
        private List<T> Retrieve(List<T> returnObjects, Vector2 position, Vector2 size, Vector2 origin = new Vector2())
        {
            var node = Find(position, size, origin);
            if (node != null && !IsLeaf)
            {
                node.Retrieve(returnObjects, position, size, origin);
            }
            else if (!IsLeaf)
            {
                RetrieveAll(returnObjects);
            }
            else
            {
                returnObjects.AddRange(Objects);
            }
            return returnObjects;
        }

        private List<T> RetrieveAll(List<T> returnObjects)
        {
            returnObjects.AddRange(Objects);
            if (TopLeft != null)
            {
                TopLeft.RetrieveAll(returnObjects);
            }
            if (TopRight != null)
            {
                TopRight.RetrieveAll(returnObjects);
            }
            if (BottomLeft != null)
            {
                BottomLeft.RetrieveAll(returnObjects);
            }
            if (BottomRight != null)
            {
                BottomRight.RetrieveAll(returnObjects);
            }
            return returnObjects;
        }

        /// <summary>
        /// Remover objeto do QuadTree ou seus filhos.
        /// </summary>
        /// <param name="obj">Objeto a ser removido.</param>
        /// <param name="origin">Posição de Origem do objeto, se possuir.</param>
        /// <returns>Boleana informando True se foi removido com sucesso, ou False se não.</returns>
        public bool Remove(T obj, Vector2 origin = new Vector2())
        {
            var node = Find(obj.PositionProperties.Position, obj.SizeProperties.Size, origin);
            if (node != null && !IsLeaf)
            {
                return node.Remove(obj, origin);
            }
            return Objects.Remove(obj);
        }

        /// <summary>
        /// Remover objeto do QuadTree ou seus filhos, usando uma posição anterior..
        /// </summary>
        /// <param name="obj">Objeto a ser removido.</param>
        /// <param name="previous">Posição anterior do objeto.</param>
        /// <param name="origin">Posição de Origem do objeto, se possuir.</param>
        /// <returns>Boleana informando True se foi removido com sucesso, ou False se não.</returns>
        public bool Remove(T obj, Vector2 previous, Vector2 origin = new Vector2())
        {
            var node = Find(previous, obj.SizeProperties.Size, origin);
            if (node != null && !IsLeaf)
            {
                return node.Remove(obj, previous, origin);
            }
            return Objects.Remove(obj);
        }

        /// <summary>
        /// Remapear objeto dentro do QuadTree, após ser movido.
        /// Este será removido do QuadTree, e re-adicionado.
        /// </summary>
        /// <param name="obj">Objeto a ser movido.</param>
        /// <param name="previous">Posição anterior do objeto.</param>
        /// <param name="origin">Posição de Origem do objeto, se possuir.</param>
        public void Moved(T obj, Vector2 previous, Vector2 origin = new Vector2())
        {
            Remove(obj, previous, origin);
            Add(obj);
        }

        /// <summary>
        /// QuadTree é uma folha.
        /// </summary>
        public bool IsLeaf
        {
            get
            {
                if (TopLeft == null)
                {
                    return true;
                }
                return false;
            }
        }

        /// <summary>
        /// Capacidade do QuadTree.
        /// </summary>
        public int Capacity
        {
            get;
            protected set;
        }

        /// <summary>
        /// Nivem máximo do QuadTree.
        /// </summary>
        public int MaxLevel
        {
            get;
            protected set;
        }

        /// <summary>
        /// Nivel do QuadTree.
        /// </summary>
        public int Level
        {
            get;
            protected set;
        }

        /// <summary>
        /// Lista de Objetos dentro do QuadTree.
        /// </summary>
        public List<T> Objects
        {
            get;
            protected set;
        }

        /// <summary>
        /// Região do QuadTree.
        /// </summary>
        public RectangleF Bounds
        {
            get;
            protected set;
        }

        /// <summary>
        /// Filho do topo esquerdo.
        /// </summary>
        public Quadtree<T> TopLeft
        {
            get;
            protected set;
        }

        /// <summary>
        /// Filho do topo direito.
        /// </summary>
        public Quadtree<T> TopRight
        {
            get;
            protected set;
        }

        /// <summary>
        /// Filho do inferior esquerdo.
        /// </summary>
        public Quadtree<T> BottomLeft
        {
            get;
            protected set;
        }

        /// <summary>
        /// Filho do inferior direito.
        /// </summary>
        public Quadtree<T> BottomRight
        {
            get;
            protected set;
        }
    }
}
